0720. 词典中最长的单词【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 哈希集合

1. 📝 题目描述

• leetcode

给出一个字符串数组 words 组成的一本英语词典。返回能够通过 words 中其它单词逐步添加一个字母来构造得到的 words 中最长的单词。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。

---

示例 1：

输入：words = ["w","wo","wor","worl", "world"]
输出："world"
解释：单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。

示例 2：

输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"

---

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• 所有输入的字符串 words[i] 都只包含小写字母。

2. 🎯 s.1 - 排序 + 哈希集合

c

int cmpStr(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

char* longestWord(char** words, int wordsSize) {
    qsort(words, wordsSize, sizeof(char*), cmpStr);
    // 简化实现：用数组存储已确认的单词
    char** set = (char**)malloc(sizeof(char*) * (wordsSize + 1));
    int setSize = 0;
    set[setSize++] = ""; // 空前缀
    char* res = "";
    for (int i = 0; i < wordsSize; i++) {
        int len = strlen(words[i]);
        // 检查 words[i][0..len-2] 是否在 set 中
        int found = 0;
        for (int j = 0; j < setSize; j++) {
            if ((int)strlen(set[j]) == len - 1 && strncmp(set[j], words[i], len - 1) == 0) {
                found = 1; break;
            }
        }
        if (found) {
            set[setSize++] = words[i];
            if (len > (int)strlen(res)) res = words[i];
        }
    }
    free(set);
    return res;
}

js

/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function (words) {
  words.sort()
  const set = new Set([''])
  let res = ''
  for (const w of words) {
    if (set.has(w.slice(0, -1))) {
      set.add(w)
      if (w.length > res.length) res = w
    }
  }
  return res
}

py

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()
        built = {''}
        res = ''
        for w in words:
            if w[:-1] in built:
                built.add(w)
                if len(w) > len(res):
                    res = w
        return res

• 时间复杂度：$O(n\times l\times \log n)$，其中 n 是单词数，l 是单词平均长度
• 空间复杂度：$O(n\times l)$

算法思路：

• 对单词字典序排序，保证短单词先被处理
• 维护哈希集合存储可逐步构建的单词
• 若当前单词去掉最后一个字符后在集合中，则加入集合并更新答案